package com.ShangGuiGu.LinkedList;

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;

/**
 * @auther zsj
 * @Date 2021/12/15
 * 双向链表和单向链表的区别在于,
 * 单向链表是单指向的,单向链表只有一个next域来表示后一个数据节点
 * 双向链表是双指向的，双向链表在单向链表的基础上多了一个pre，指向自己本身的前一个节点
 * 所以单向链表不能实现自我删除，而双向链表可以实现自我删除
 * <p>
 * 因为删除需要修改前一个节点的next域为当前节点的next域    ！important
 * 所以 我们用temp表示当前域，temp.pre.next =temp.next   ！important
 * 你还需要将temp的后一个节点的pre修改为temp.pre          ！important
 * 这样temp本身就会被垃圾回收机制回收，就完成了删除的功能
 **/


/**
 * Test类
 */
public class TwinLinkedListDemo {
    public static void main(String[] args) {
        //测试
        HeroNodeTwin heroNode1 = new HeroNodeTwin(1, "猪猪侠1", "pigMan1");
        HeroNodeTwin heroNode4 = new HeroNodeTwin(4, "猪猪侠4", "pigMan4");
        HeroNodeTwin heroNode2 = new HeroNodeTwin(2, "猪猪侠2", "pigMan2");
        HeroNodeTwin heroNode3 = new HeroNodeTwin(3, "猪猪侠3", "pigMan3");
        //创捷链表
        TwinLinkedList twinlinkedlist = new TwinLinkedList();
        twinlinkedlist.addByOrder(heroNode1);
        twinlinkedlist.addByOrder(heroNode2);
        twinlinkedlist.addByOrder(heroNode3);
        twinlinkedlist.addByOrder(heroNode4);

        HeroNodeTwin heroNodeTwin = new HeroNodeTwin();
        heroNodeTwin.no=3;
        heroNodeTwin.name="笨蛋";
        heroNodeTwin.nickName="傻瓜";
        twinlinkedlist.update(heroNodeTwin);
        twinlinkedlist.delete(4);
        twinlinkedlist.list();

    }
}

/**
 * 双向链表的类
 */
class TwinLinkedList {
    //先初始化头节点，头节点不能动
    private HeroNodeTwin head = new HeroNodeTwin(0, "", "");//next和pre都默认为null


    public HeroNodeTwin getHead() {
        return head;
    }

    //增加到双向链表的尾部
    public void insertListEnd(HeroNodeTwin node) {
        /**
         * 思路
         * 找到双向的最后一个节点,将其next域指向当前传入的temo节点
         */
        HeroNodeTwin temp = head;//拿到头节点
        while (true) {
            if (temp.next == null) {
                //说明找到最后一位了
                break;
            }
            //未找到需要往后移
            temp = temp.next;
        }
        temp.next = node;//将最后一个数据的指向转为当前数据
        node.pre = temp;//将前指向域变为前一个
    }

    //增加的自定义位置
    public void addByOrder(HeroNodeTwin node) {
        //头节点不能动
        HeroNodeTwin temp = head;
        //添加的编号是否存在,默认不存在
        boolean flag = false;
        /////////////
        while (true) {
            if (temp.next == null) {
                //说明temp已经在链表最后了
                break;
            }
            //如果temp的编号大于传入的编号，说明传入的编号在temp的后面
            if (temp.no > node.no) {
                break;
            } else if (temp.no == node.no) {
                flag = true;
                break;
            }
            temp = temp.next;//后移
        }
        /////////////
        if (flag) {
            System.out.printf("编号%d已经存在，无法添加\n", node.no);
        } else {
            //可以添加，temp后面
            //因为新节点一定是在temp的后面

            node.next=temp.next;
            node.pre =temp;
            temp.next =node;
            if (node.next !=null){
                node.next.pre=node;
            }
        }
    }

    //删除
    //双向链表删除可以自身删除,我们只需要在找到改编号的数据时，
    // 修改当前temp的pre和next指向域即可
    public void delete(int no) {
        //判断是否为空
        if (head.next == null) {
            //链表为空
            System.out.println("链表为空，你删个锤子");
            return;
        }
        HeroNodeTwin temp = head.next;
        boolean flag = false;//节点中是否含有信息
        while (true) {
            if (temp == null) {
                //说明节点到最后一个为空
                //没找到 也没法找
                break;
            }
            if (temp.no == no) {
                //数据存在
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag) {
            //双向链表修改自身的属性
            //temp的前一个节点的next域等于temp当前的next域
            //temp的next域的pre等于temp.pre
            //这样做，temp就不复存在
            temp.pre.next = temp.next;
            //加一个判断，防止删除的节点是最后一个节点
            //不加判断，你的temp.next域是空的，那就会报空指针异常
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }
        } else {
            System.out.printf("编号为%d的节点不存在\n", no);
        }
    }

    //修改
    public void update(HeroNodeTwin newHeroNode) {
        if (head.next == null) {
            //说明链表没有节点
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点
        HeroNodeTwin temp = head.next;
        boolean flag = false;//是否找到该节点
        while (true) {
            if (temp == null) {
                break;//链表到最后一个节点了
            }
            if (temp.no == newHeroNode.no) {
                //找到了
                flag = true;
                break;
            }
            temp = temp.next;//没有找到就往后移动继续找
        }
        if (flag) {
            //修改
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        } else {
            //没有找到
            System.out.printf("没有找到编号%d的节点，不能修改\n", newHeroNode.no);
        }


    }

    //遍历
    public void list() {
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动，需要一个辅助变量来遍历
        HeroNodeTwin temp = head.next;
        while (true) {
            //判断是否到链表的最后
            if (temp == null) {
                break;
            }
            //输出节点信息，不为空的情况
            System.out.println(temp);
            //将next后移
            temp = temp.next;
        }
    }

}

//定义英雄属性类，每一个heroNode就是一个节点
//节点域类
@Data
@AllArgsConstructor
@NoArgsConstructor
class HeroNodeTwin {
    public int no;//编号
    public String name;//名字
    public String nickName;//绰号
    public HeroNodeTwin next;//next指向域
    public HeroNodeTwin pre;//pre前指向域

    public HeroNodeTwin(int no, String name, String nickName) {
        this.no = no;
        this.name = name;
        this.nickName = nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                ", nickName='" + nickName + '}';
    }


}

